package leetcode.Leetcode42;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

class DraftSolution {
    //动态规划
    public int trap(int[] height) {
        //构建两个数组，一个保存其左边最高的值，一个保存其右边最大的值
        int n = height.length;
        if (n==0) {
            return 0;
        }
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n-2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans+=Math.min(leftMax[i],rightMax[i])-height[i];
        }
        return ans;
    }

    //单调栈
    /*
    思想：将下标一直入栈，如果是小于或者等于栈顶元素，都不用计算其宽度，如果大于，则计算一下其能接雨水的面积
     */
    public int trap1(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {//栈不为空并且高度上升
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();//这里这个left是左边最高的
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }

    public static void main(String[] args) {
        DraftSolution draftSolution = new DraftSolution();
        draftSolution.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
    }
}